This video provides an introductory lecture to Binary Heap.
This track of the course covers the topic "Heap".
In details, this track will cover:
Objective: The objective of this track is to familiarize the learners with Heaps.
Track Content:
Assessment: All Tracks in every week are associated with weekly contests.
This video provides an introductory lecture to Binary Heap.
This video discusses the implementation of a Binary Heap.
Codes:
This video implements the insertion method of Binary Heap.
Codes:
This video discusses the Heapify and Extract operation and how can it be implemented in a Binary Heap.
Codes:
This video discusses the Decrease Key, Delete and Build Heap operation of Binary Heap.
Codes:
Working of Heap Sort with implementation.
Codes:
This video discusses the working and implementation of the Priority Queue in C++. It also discusses the various general applications of Priority Queue.
Codes:
This video explains the implementation of the Priority Queue in Java.
Codes:
This video discusses the problem of how to Sort an array that is already k-sorted.
Codes:
This video discusses the problem of buying the maximum items with a given sum.
Codes:
This video discusses the problem of calculating the K Largest Elements in an unsorted array
Codes:
This video discusses the problem of how to Merge K Sorted Arrays.
Codes:
This video discusses the calculation of a Median of a Stream.
Codes:

Representing Binary Heaps
Since a Binary Heap is a complete Binary Tree, it can be easily represented using Arrays.| Arr[(i-1)/2] | Returns the parent node |
| Arr[(2*i)+1] | Returns the left child node |
| Arr[(2*i)+2] | Returns the right child node |
Heapifying an Element
Generally, on inserting a new element onto a Heap, it does not satisfy the property of Heap as stated above on its own. The process of placing the element at the correct location so that it satisfies the Heap property is known as Heapify.


Given a Binary Heap and an element present in the given Heap. The task is to delete an element from this Heap.
Suppose the Heap is a Max-Heap as:
The element to be deleted is root, i.e. 10.
Process:
The last element is 4.
Step 1: Replace the last element with root, and delete it.
Step 2: Heapify root.
Final Heap:![]()
// C++ program for implement deletion in Heaps
#include <iostream>
using namespace std;
// To heapify a subtree rooted with node i which is
// an index in arr[]. N is size of heap
void heapify(int arr[], int n, int i)
{
int largest = i; // Initialize largest as root
int l = 2 * i + 1; // left = 2*i + 1
int r = 2 * i + 2; // right = 2*i + 2
// If left child is larger than root
if (l < n && arr[l] > arr[largest])
largest = l;
// If right child is larger than largest so far
if (r < n && arr[r] > arr[largest])
largest = r;
// If largest is not root
if (largest != i) {
swap(arr[i], arr[largest]);
// Recursively heapify the affected sub-tree
heapify(arr, n, largest);
}
}
// Function to delete the root from Heap
void deleteRoot(int arr[], int& n)
{
// Get the last element
int lastElement = arr[n - 1];
// Replace root with first element
arr[0] = lastElement;
// Decrease size of heap by 1
n = n - 1;
// heapify the root node
heapify(arr, n, 0);
}
/* A utility function to print array of size n */
void printArray(int arr[], int n)
{
for (int i = 0; i < n; ++i)
cout << arr[i] << " ";
cout << "\n";
}
// Driver Code
int main()
{
// Array representation of Max-Heap
// 10
// / \
// 5 3
// / \
// 2 4
int arr[] = { 10, 5, 3, 2, 4 };
int n = sizeof(arr) / sizeof(arr[0]);
deleteRoot(arr, n);
printArray(arr, n);
return 0;
}
// Java program for implement deletion in Heaps
public class deletionHeap {
// To heapify a subtree rooted with node i which is
// an index in arr[].Nn is size of heap
static void heapify(int arr[], int n, int i)
{
int largest = i; // Initialize largest as root
int l = 2 * i + 1; // left = 2*i + 1
int r = 2 * i + 2; // right = 2*i + 2
// If left child is larger than root
if (l < n && arr[l] > arr[largest])
largest = l;
// If right child is larger than largest so far
if (r < n && arr[r] > arr[largest])
largest = r;
// If largest is not root
if (largest != i) {
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
// Recursively heapify the affected sub-tree
heapify(arr, n, largest);
}
}
// Function to delete the root from Heap
static int deleteRoot(int arr[], int n)
{
// Get the last element
int lastElement = arr[n - 1];
// Replace root with first element
arr[0] = lastElement;
// Decrease size of heap by 1
n = n - 1;
// heapify the root node
heapify(arr, n, 0);
// return new size of Heap
return n;
}
/* A utility function to print array of size N */
static void printArray(int arr[], int n)
{
for (int i = 0; i < n; ++i)
System.out.print(arr[i] + " ");
System.out.println();
}
// Driver Code
public static void main(String args[])
{
// Array representation of Max-Heap
// 10
// / \
// 5 3
// / \
// 2 4
int arr[] = { 10, 5, 3, 2, 4 };
int n = arr.length;
n = deleteRoot(arr, n);
printArray(arr, n);
}
}5 4 3 2
Let us try deleting 30 from below Min Heap
We replace 30 with -INF
We move -INF to root by swapping with parent
nodes one by one
Now Delete Root (We first replace it with last node
then call heapify)![]()
Given a Binary Heap and a new element to be added to this Heap. The task is to insert the new element to the Heap maintaining the properties of Heap.
Suppose the Heap is a Max-Heap as:
The new element to be inserted is 15.
Process:
Step 1: Insert the new element at the end.
Step 2: Heapify the new element following bottom-up
approach.
-> 15 is less than its parent 3, swap them.
-> 15 is again less than its parent 10, swap them.
Therefore, the final heap after insertion is:
-> 15 is less than its parent 3, swap them.
// C++ program to insert new element to Heap
#include <iostream>
using namespace std;
#define MAX 1000 // Max size of Heap
// Function to heapify ith node in a Heap
// of size n following a Bottom-up approach
void heapify(int arr[], int n, int i)
{
// Find parent
int parent = (i - 1) / 2;
if (parent >= 0) {
// For Max-Heap
// If current node is greater than its parent
// Swap both of them and call heapify again
// for the parent
if (arr[i] > arr[parent]) {
swap(arr[i], arr[parent]);
// Recursively heapify the parent node
heapify(arr, n, parent);
}
}
}
// Function to insert a new node to the Heap
void insertNode(int arr[], int& n, int Key)
{
// Increase the size of Heap by 1
n = n + 1;
// Insert the element at end of Heap
arr[n - 1] = Key;
// Heapify the new node following a
// Bottom-up approach
heapify(arr, n, n - 1);
}
// A utility function to print array of size n
void printArray(int arr[], int n)
{
for (int i = 0; i < n; ++i)
cout << arr[i] << " ";
cout << "\n";
}
// Driver Code
int main()
{
// Array representation of Max-Heap
// 10
// / \
// 5 3
// / \
// 2 4
int arr[MAX] = { 10, 5, 3, 2, 4 };
int n = 5;
int key = 15;
insertNode(arr, n, key);
printArray(arr, n);
// Final Heap will be:
// 15
// / \
// 5 10
// / \ /
// 2 4 3
return 0;
}
// Java program for implement insertion in Heaps
public class insertionHeap {
private int[] arr;
private int size;
private int maxsize;
// Constructor to initialize an
// empty max heap with maximum capacity.
public insertionHeap()
{
this.maxsize = 1000;
this.size = -1;
arr = new int[this.maxsize + 1];
}
// To heapify a subtree rooted with node i which is
// an index in arr[].Nn is size of heap
private void heapify(int i)
{
int n=size+1 ;
// Find parent
int parent = (i - 1) / 2;
if (parent >= 0) {
// For Max-Heap
// If current node is greater than its parent
// Swap both of them and call heapify again
// for the parent
if (arr[i] > arr[parent]) {
int temp=arr[parent];
arr[parent]=arr[i];
arr[i]=temp;
// swap
// Recursively heapify the parent node
heapify(parent);
}
}
}
// Function to insert key to heap
// Inserts a new element to max heap
public void insert(int element)
{
arr[++size] = element;
if(size>0)
heapify(size);
}
/* A utility function to print array of size N */
public void printArray()
{
for (int i = 0; i <= size; ++i)
System.out.print(arr[i] + " ");
System.out.println();
}
// Driver Code
public static void main(String args[])
{
// Array representation of Max-Heap
// 10
// / \
// 5 3
// / \
// 2 4
insertionHeap h = new insertionHeap();
h.insert(10);
h.insert(5);
h.insert(3);
h.insert(2);
h.insert(4);
h.insert(15);
h.printArray();
}
}15 5 10 2 4 3
Given N elements. The task is to build a Binary Heap from the given array. The heap can be either Max Heap or Min Heap.
Root is at index 0 in array.
Left child of i-th node is at (2*i + 1)th index.
Left child of i-th node is at (2*i + 2)th index.
Parent of i-th node is at (i-1)/2 index.
Last non-leaf node = parent of last-node.
or, Last non-leaf node = parent of node at (n-1)th index.
or, Last non-leaf node = Node at index ((n-1) - 1)/2.
= (n - 2)/2.
Array = {1, 3, 5, 4, 6, 13, 10, 9, 8, 15, 17}
Corresponding Complete Binary Tree is:

The task to build a Max-Heap from above array.
Total Nodes = 11.
Last Non-leaf node index = (11/2) - 1 = 4.
Therefore, last non-leaf node = 6.
To build the heap, heapify only the nodes:
[1, 3, 5, 4, 6] in reverse order.
Heapify 6: Swap 6 and 17.

Heapify 4: Swap 4 and 9.

Heapify 5: Swap 13 and 5.

Heapify 3: First Swap 3 and 17, again swap 3 and 15.

Heapify 1: First Swap 1 and 17, again swap 1 and 15,
finally swap 1 and 6.

// C++ program for building Heap from Array
#include <iostream>
using namespace std;
// To heapify a subtree rooted with node i which is
// an index in arr[]. N is size of heap
void heapify(int arr[], int n, int i)
{
int largest = i; // Initialize largest as root
int l = 2 * i + 1; // left = 2*i + 1
int r = 2 * i + 2; // right = 2*i + 2
// If left child is larger than root
if (l < n && arr[l] > arr[largest])
largest = l;
// If right child is larger than largest so far
if (r < n && arr[r] > arr[largest])
largest = r;
// If largest is not root
if (largest != i) {
swap(arr[i], arr[largest]);
// Recursively heapify the affected sub-tree
heapify(arr, n, largest);
}
}
// Function to build a Max-Heap from the given array
void buildHeap(int arr[], int n)
{
// Index of last non-leaf node
int startIdx = (n - 2)/2;
// Perform reverse level order traversal
// from last non-leaf node and heapify
// each node
for(int i = startIdx; i>=0; i--)
{
heapify(arr, n, i);
}
}
// A utility function to print the array
// representation of Heap
void printHeap(int arr[], int n)
{
cout<<"Array representation of Heap is:\n";
for (int i = 0; i < n; ++i)
cout << arr[i] << " ";
cout << "\n";
}
// Driver Code
int main()
{
// Binary Tree Representation
// of input array
// 1
// / \
// 3 5
// / \ / \
// 4 6 13 10
// / \ / \
// 9 8 15 17
int arr[] = {1, 3, 5, 4, 6, 13, 10, 9, 8, 15, 17};
int n = sizeof(arr) / sizeof(arr[0]);
buildHeap(arr, n);
printHeap(arr, n);
// Final Heap:
// 17
// / \
// 15 13
// / \ / \
// 9 6 5 10
// / \ / \
// 4 8 3 1
return 0;
}
// Java program for building Heap from Array
public class BuildHeap {
// To heapify a subtree rooted with node i which is
// an index in arr[].Nn is size of heap
static void heapify(int arr[], int n, int i)
{
int largest = i; // Initialize largest as root
int l = 2 * i + 1; // left = 2*i + 1
int r = 2 * i + 2; // right = 2*i + 2
// If left child is larger than root
if (l < n && arr[l] > arr[largest])
largest = l;
// If right child is larger than largest so far
if (r < n && arr[r] > arr[largest])
largest = r;
// If largest is not root
if (largest != i) {
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
// Recursively heapify the affected sub-tree
heapify(arr, n, largest);
}
}
// Function to build a Max-Heap from the Array
static void buildHeap(int arr[], int n)
{
// Index of last non-leaf node
int startIdx = (n - 2)/2;
// Perform reverse level order traversal
// from last non-leaf node and heapify
// each node
for(int i = startIdx; i>=0; i--)
{
heapify(arr, n, i);
}
}
// A utility function to print the array
// representation of Heap
static void printHeap(int arr[], int n)
{
System.out.println("Array representation of Heap is:");
for (int i = 0; i < n; ++i)
System.out.print(arr[i] + " ");
System.out.println();
}
// Driver Code
public static void main(String args[])
{
// Binary Tree Representation
// of input array
// 1
// / \
// 3 5
// / \ / \
// 4 6 13 10
// / \ / \
// 9 8 15 17
int arr[] = {1, 3, 5, 4, 6, 13, 10,
9, 8, 15, 17};
int n = arr.length;
buildHeap(arr, n);
printHeap(arr, n);
}
}Array representation of Heap is:
17 15 13 9 6 5 10 4 8 3 1
priority_queue< type_of_data > name_of_heap;
priority_queue< type, vector<type>, greater<type> > name_of_heap;
// C++ program to implement Max Heap and Min Heap
// using priority_queue in C++ STL
#include <iostream>
#include <queue>
using namespace std;
int main ()
{
// DECLARING MAX HEAP
priority_queue <int> max_heap;
// Add elements to the Max Heap
// in any order
max_heap.push(10);
max_heap.push(30);
max_heap.push(20);
max_heap.push(5);
max_heap.push(1);
// Print element at top of the heap
// every time and remove it until the
// heap is not empty
cout<<"Element at top of Max Heap at every step:\n";
while(!max_heap.empty())
{
// Print Top Element
cout<<max_heap.top()<<" ";
// Remove Top Element
max_heap.pop();
}
// DECLARING MIN HEAP
priority_queue <int, vector<int>, greater<int> > min_heap;
// Add elements to the Min Heap
// in any order
min_heap.push(10);
min_heap.push(30);
min_heap.push(20);
min_heap.push(5);
min_heap.push(1);
// Print element at top of the heap
// every time and remove it until the
// heap is not empty
cout<<"\n\nElement at top of Min Heap at every step:\n";
while(!min_heap.empty())
{
// Print Top Element
cout<<min_heap.top()<<" ";
// Remove Top Element
min_heap.pop();
}
return 0;
} Element at top of Max Heap at every step:
30 20 10 5 1
Element at top of Min Heap at every step:
1 5 10 20 30
Queue<Integer> max_heap = new PriorityQueue<>(
Collections.reverseOrder());
Queue<Integer> min_heap = new PriorityQueue<>();
// Java Program to implement Max heap and Min heap
// using the PriorityQueue class
import java.util.*;
import java.io.*;
import java.lang.*;
class GFG
{
public static void main (String[] args) {
// DECLARING MAX HEAP
Queue<Integer> max_heap = new PriorityQueue<>(
Collections.reverseOrder());
// Add elements to the Max Heap
// in any order
max_heap.add(10);
max_heap.add(30);
max_heap.add(20);
max_heap.add(5);
max_heap.add(1);
// Print element at top of the heap
// every time and remove it until the
// heap is not empty
System.out.print("Element at top of Max Heap at"
+ " every step:\n");
while(!max_heap.isEmpty())
{
// Print Top Element
System.out.print(max_heap.peek()+" ");
// Remove Top Element
max_heap.poll();
}
// DECLARING MIN HEAP
Queue<Integer> min_heap = new PriorityQueue<>();
// Add elements to the Min Heap
// in any order
min_heap.add(10);
min_heap.add(30);
min_heap.add(20);
min_heap.add(5);
min_heap.add(1);
// Print element at top of the heap
// every time and remove it until the
// heap is not empty
System.out.print("\n\nElement at top of Min Heap "
+ "at every step:\n");
while(!min_heap.isEmpty())
{
// Print Top Element
System.out.print(min_heap.peek()+" ");
// Remove Top Element
min_heap.poll();
}
}
}Some error occured or ide is down,please try again
// To heapify a subtree rooted with node i which is
// an index in arr[]. n is size of heap
void heapify( arr[], n, i)
{
largest = i // Initialize largest as root
l = 2*i + 1 // left = 2*i + 1
r = 2*i + 2 // right = 2*i + 2
// If left child is larger than root
if (l < n && arr[l] > arr[largest])
largest = l
// If right child is larger than largest so far
if (r < n && arr[r] > arr[largest])
largest = r
// If largest is not root
if (largest != i)
{
swap(arr[i], arr[largest])
// Recursively heapify the affected sub-tree
heapify(arr, n, largest)
}
}
// main function to do heap sort
void heapSort( arr[], n)
{
// Build heap (rearrange array)
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i)
// One by one extract an element from heap
for (int i=n-1; i>=0; i--)
{
// Move current root to end
swap(arr[0], arr[i])
// call max heapify on the reduced heap
heapify(arr, i, 0)
}
}
void MinHeap( a[], size)
{
heap_size = size
harr = a // store address of array
int i = (heap_size - 1)/2
while (i >= 0)
{
MinHeapify(i)
i--
}
}
// Method to remove minimum element (or root) from min heap
int extractMin()
{
if (heap_size == 0)
return INT_MAX
// Store the minimum vakue.
int root = harr[0]
// If there are more than 1 items, move the last item to root
// and call heapify.
if (heap_size > 1)
{
harr[0] = harr[heap_size-1]
MinHeapify(0)
}
heap_size--
return root
}
// A recursive method to heapify a subtree with root at given index
// This method assumes that the subtrees are already heapified
void MinHeapify(int i)
{
int l = left(i)
int r = right(i)
int smallest = i;
if (l < heap_size && harr[l] < harr[i])
smallest = l
if (r < heap_size && harr[r] < harr[smallest])
smallest = r
if (smallest != i)
{
swap(& harr[i], & harr[smallest])
MinHeapify(smallest)
}
}
// Returns Minimum Element
int getMin()
{
return harr[0]
}
// Function to return k'th smallest element in a given array
int kthSmallest( arr[], n, k)
{
// Build a heap of n elements: O(n) time
MinHeap(arr, n)
// Do extract min (k-1) times
for (int i=0; i < k-1; i++)
extractMin()
// Return root
return getMin()
}
What is Median?
Median can be defined as the element in the data set which separates the higher half of the data sample from the lower half. In other words we can get the median element as, when the input size is odd, we take the middle element of sorted data. If the input size is even, we pick average of middle two elements in sorted stream.Input: 5 10 15Explanation: Given the input stream as an array of integers [5,10,15]. We will now read integers one by one and print the median correspondingly. So, after reading first element 5, the median is 5. After reading 10,median is 7.5 After reading 15 ,median is 10.
Output: 5
7.5
10
// function to calculate median of streamTime Complexity: O(n Log n)
void printMedian(double arr[], int n)
{
// max heap to store the smaller half elements
priority_queues;
// min heap to store the greater half elements
priority_queue,greater > g;
double med = arr[0];
s.push(arr[0]);
print(med)
// reading elements of stream one by one
/* At any time we try to make heaps balanced and
their sizes differ by at-most 1. If heaps are
balanced,then we declare median as average of
min_heap_right.top() and max_heap_left.top()
If heaps are unbalanced,then median is defined
as the top element of heap of larger size */
for (int i=1; i < n; i++)
{
double x = arr[i];
// case1(left side heap has more elements)
if (s.size() > g.size())
{
if (x < med)
{
g.push(s.top());
s.pop();
s.push(x);
}
else
g.push(x);
med = (s.top() + g.top())/2.0;
}
// case2(both heaps are balanced)
else if (s.size()==g.size())
{
if (x < med)
{
s.push(x);
med = (double)s.top();
}
else
{
g.push(x);
med = (double)g.top();
}
}
// case3(right side heap has more elements)
else
{
if (x > med)
{
s.push(g.top());
g.pop();
g.push(x);
}
else
s.push(x);
med = (s.top() + g.top())/2.0;
}
print(med)
}
}
Asked In: Cisco
Asked In: Amazon
Asked In: Amazon
A | 1, 3, 5, 6, 8, 9 |
B | 9, 6, 3, 1, 8, 5 |
C | 9, 3, 6, 8, 5, 1 |
D | 9, 5, 6, 8, 3, 1 |